#include<iostream>
using namespace std;
#define FOR(x) for(int i=map[x];~i;i=stor[i].next)
#define Tree(a) root[belong[a]], 1, 1, length[belong[a]] 
#define Left fro,(u<<1),l,mid
#define Right fro,(u<<1)+1,mid+1,r
#define si stor[i]
const int MN=10010;
const int Log=15;
const int inf=0x3fffffff;
struct node{
	int v,w,id,next;
	node(){}
	node(int a,int b,int c,int d):v(a),w(b),id(c),next(d){}
}stor[3*MN];
int neww,map[MN],weight[MN],depth[MN],sum[MN],n;
int tmax[5*MN],root[5*MN],op,id2v[MN];
int belong[MN],pos[MN],length[MN],anc[MN][Log];

void add(int s,int t,int i,int w){
	stor[neww]=node(t,w,i,map[s]);map[s]=neww++;
	stor[neww]=node(s,w,i,map[t]);map[t]=neww++;
}
int NewST(int len){//计算偏移量
	op+=4*len;
	return op-4*len;
}
void fix(int fro,int u,int l,int r,int p,int w){//fro树根,u偏移量 
	if(l==r){
		tmax[fro+u]=w;return;//fro树跟偏移量+当前的节点在这个树的u偏移量
	}
	int mid=(l+r)>>1;
	if(p>mid)fix(Right,p,w);
	else fix(Left,p,w);
	tmax[fro+u]=max(tmax[fro+(u<<1)],tmax[fro+1+(u<<1)]);
}
int getmax(int fro,int u,int l,int r,int ll,int rr){//fro树根,u偏移量 
	if(ll<=l&&rr>=r)return tmax[fro+u];
	int mid=(l+r)>>1;
	if(rr<=mid)return getmax(Left,ll,rr);
	if(ll>mid)return getmax(Right,ll,rr);
	return max(getmax(Left,ll,mid),getmax(Right,mid+1,rr));
}
void dfs1(int u,int fa){
	sum[u]=1;anc[u][0]=fa;depth[u]=depth[fa]+1;
	for(int i=1;i<Log&&anc[u][i-1];i++)
		anc[u][i]=anc[anc[u][i-1]][i-1];
	FOR(u)if(si.v!=fa){
		weight[si.v]=si.w;//
		id2v[si.id]=si.v;//
		dfs1(si.v,u);
		sum[u]+=sum[si.v];
	}
}
void dfs2(int u,int len,int fa){
	int ma=0,tem=0;
	FOR(u)if(si.v!=fa&&sum[si.v]>ma)
		ma=sum[si.v],tem=si.v;
	if(!tem){
		int p,i;
		for(p=u,i=len-1;i;i--)p=anc[p][0];
		root[p]=NewST(len);//root 记录树根在原来的表中的相对位置
		length[p]=len;
		for(i=len;i;i--,u=anc[u][0]){
			belong[u]=p;pos[u]=i;
			fix(Tree(u),i,weight[u]);
		}
		return;
	}
	dfs2(tem,len+1,u);
	FOR(u)if(si.v!=fa&&si.v!=tem)
		dfs2(si.v,1,u);
}
void BuildTree(){
	memset(anc,0,sizeof(anc));
	depth[0]=0;weight[1]=0-inf;
	dfs1(1,0);
	memset(tmax,0,sizeof(tmax));//-inf
	dfs2(1,1,0);
}
int LCA(int a,int b){
	if(depth[a]>depth[b])swap(a,b);
	for(int t=depth[b]-depth[a],k=0;k<Log;k++)
		if(t&(1<<k))b=anc[b][k];
	if(a==b)return a;
	for(int k=Log-1;k>=0;k--)if(anc[a][k]!=anc[b][k])
		a=anc[a][k],b=anc[b][k]; 
	return anc[a][0];
}
void Change(int id,int w){
	weight[id2v[id]]=w;
	fix(Tree(id2v[id]),pos[id2v[id]],w);
}
inline void Up(int &a, int b) {if (a < b) a = b;}
int Query(int a,int b){
	int res=-inf;
	while(a!=b){
		if(belong[a]!=belong[b]){
			Up(res,getmax(Tree(b),1,pos[b]));
			b=anc[belong[b]][0];
		}else{
			Up(res,getmax(Tree(b),pos[a]+1,pos[b]));
			break;
		}
	}
	return res;
}
void solove(){
	int s,t,w,i;
	scanf("%d",&n);
	neww=op=1;
	for(i=1;i<=n;i++)map[i]=-1;
	for(i=1;i<n;i++){
		scanf("%d%d%d",&s,&t,&w);
		add(s,t,i,w);
	}
	BuildTree();
	static char cmd[100];
	while(scanf("%s",cmd)){
        if(cmd[0]=='D')break;
        scanf("%d%d",&s,&t);
        if(cmd[0]=='Q'){
         	int c=LCA(s,t);
		    printf("%d\n",max(Query(c,s),Query(c,t)));
        }else Change(s,t);
	}
}
int main(){
	int TC,flag;
	scanf("%d",&TC);flag=0;
	while(TC--){
		if(!flag)flag=1;
		else printf("\n");
		solove();
	}
}

